
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-07
 * Time: 22:55
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class Solution {
    // 中序 dfs
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root==null){
            return null;
        }
        TreeNode left = inorderSuccessor(root.left, p);
        // 左子树返回的结果不为空, 说明已经找到答案
        if(left != null){
            return left;
        }
        // 根据二叉搜索树的性质, 只要节点 > p.val 就返回该节点
        // 那么这个节点一定是 p 的后继节点
        if(root.val > p.val){
            return root;
        }
        // 右子树返回的结果不为空, 说明已经找到答案
        TreeNode right = inorderSuccessor(root.right, p);
        // 直接返回右子树返回的结果即可
        return right;

    }
}
